# 132模式: https://leetcode-cn.com/problems/132-pattern/

# 最基本的暴力破解： O(n^3) 超时
class Solution:
    def find132pattern(self, nums: list) -> bool:
        """
            普通解法： 直接暴力遍历三个数，找到符合条件的. 期间可以判断一下， i j 必须符合条件才去招合适的 k
        """
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                # nums[j] > nums[i] 才继续
                if nums[j] < nums[i]: continue
                for k in range(j + 1, n):
                    if nums[k] > nums[i] and nums[k] < nums[j]:
                        return True
                        
        return False


# 暴力破解优化，但是依旧无法通过，性能还差一些
class Solution:
    def find132pattern(self, nums: list) -> bool:
        """
            暴力解法优化， O(n^3)，一层循环找一个数。效率很低。 因为只需要判断是否存在 132 这种模式的数。所以我们找最有可能的就行，
            完全不需要暴力一个一个试。 首先 nums[i] < nums[k] < nums[j]   nums[i] 是最小的。 nums[k] 是最大的。 
            在第一次遍历的时候，就可以记录当前的最大值， 以及最小值。 第二次遍历的时候，就找到 nums[k] 就可以了
            这样时间复杂度变为了 O(n^2)
        """
        n = len(nums)
        # 1. 固定 nums[i] 初始为 nums[0]
        nums_i = nums[0]
        # 2. 寻找nums[j], 并且更新nums_i为当前最小值
        for j in range(1, n):
            # 寻找大于的值
            if nums[j] > nums_i:
                for k in range(j + 1, n):
                    if nums[j] > nums[k] and nums[k] > nums_i:
                        return True

            # 更新看看当前的 nums_i为最小
            nums_i = min(nums_i, nums[j])

        return False


# 官方代码，继续上面的优化
# from sortedcontainers import SortedList
class Solution:
    def find132pattern(self, nums: list) -> bool:
        """
            # 对上面的优化，因为上面对 k的查找还是线性的一个一个找，那么我们需要改变，利用平衡树，或者红黑树
            # 进而快速进行查找j 后面位置满足条件的 k
            时间复杂度：O(nlogn)
        """
        n = len(nums)
        if n < 3:
            return False
        
        # 左侧最小值
        left_min = nums[0]
        # 右侧所有元素
        right_all = SortedList(nums[2:])
        
        for j in range(1, n - 1):
            if left_min < nums[j]:
                index = right_all.bisect_right(left_min)
                if index < len(right_all) and right_all[index] < nums[j]:
                    return True
            left_min = min(left_min, nums[j])
            # 要删除掉， 因为 当前位置 为下一次的 j， 那么他就不可能再作为 k，不能继续放到查找树中查找了
            right_all.remove(nums[j + 1])

        return False


# 代码报错了，没有理解栈的细节。。 不研究了
class Solution:
    def find132pattern(self, nums: list) -> bool:
        """
            栈优化思路： 根据前面的思路， i 可以确定为最小的值， k第二大，那么只要大于当前i值的都可以作为k
        """
        n = len(nums)
        # 算出前缀最小值（就是到当前位置，最小的值是哪个）
        minList = [0] * n
        minList[0] = nums[0]
        for i in range(1, n):
            minList[i] = min(nums[i], minList[i - 1])
        
        # 下面寻找k， 维护一个栈
        stack = list()

        # 寻找合适的 j。 下标遍历不能是第一个位置，和最后一个位置
        for j in range(n-2, 0, -1):
            # 1. 当前的j 必须大于 i,才能去寻找k
            if nums[j] > minList[j]:
                while stack and stack[-1] <= minList[j]:
                    stack.pop()
                # 2. 此时如果栈还不为空，并且栈顶元素小于nums[j],说明找到了 k 了
                if stack and nums[j] > stack[-1]:
                    return True
                
                stack.append(nums[j])

        return False
